package Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        return three(nums,3,0,0);
    }

    List<List<Integer>> three(int[] nums,int n,int start,int target){
        if(n<2||n>=nums.length) return list;
        if(n==2){
            int left=start;
            int right=nums.length-1;
            while (left<right){
                int sum=nums[left]+nums[right];
                if(sum<target){
                    left++;
                    while (left<right&&nums[left]==nums[left+1]) left++;
                }else if(sum>target){
                    right--;
                    while (left<right&&nums[right]==nums[right-1]) left--;
                }else {
                    List<Integer> list1=new ArrayList<>();
                    list1.add(nums[left]);
                    list1.add(nums[right]);

                }
            }
        }else {
            for (int i=0;i<nums.length;i++){
                List<List<Integer>> lists=three(nums,2,i,target-nums[i]);
                for (List a:lists){
                    a.add(nums[i]);
                    list.add(a);
                }
            }
        }
        return list;
    }
}
